The demands on computer systems become larger and larger with ever increasing workloads. One strategy is to divide a workload among a number of computer resources that each perform a portion of the workload. For instance, a workload maybe divided into smaller pieces that are processed individually (e.g., in parallel). Such division of work can process an overall workload that no single computer could manage.
For example, large scale services such as large scale message queuing services, database services, streaming data intake services, and the like rely upon sharding to perform large amounts of data processing. These services may be provided by a network-based service provider (e.g., “in the cloud”), for example.
For various reasons, it may be necessary to divide the workload being processed into portions, for example by association with values of a key, or the like, included in the request (e.g. a key associated with an account number, or a particular customer process, or stored object, etc.) A large number of shards may be used to process the workload. The processing may be expensive, for example database lookups of supporting material for processing based on a key, or the like, included in a request. Caching may be one way to reduce that cost. In at least some distributed load systems, each, or at least many of the shards may be required to maintain cached data associated with the keys which that shard is processing. Furthermore, key-based metrics may need to be gathered from each of the shards that performed processing for that particular key. For all of these reasons, it may be desirable to minimize the number of different portions that are processed by any one shard.
It can be difficult to achieve the desirable goal of both spreading the load across shards while having the same shard process all the requests for a particular key. For example, the overhead associated with tracking and/or routing the various keys for each of the shards may incur overhead costs. Additionally, in some instances, the workload associated with a particular key may be so great as to require more than one shard.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.